package leetcode.editor.vscdev;

import leetcode.editor.utils.*;

public class lc701 {
    /* 701. 二叉搜索树中的插入操作
     *  
     * 思路:
     *   1. 二叉搜索树中插入一个节点，那么这个节点肯定要插入到根节点的左边或者右边，
     *      所以，我们先找到这个节点应该插入的位置，然后插入即可。
     *   2. 递归实现
     *   3. 迭代实现
     *   4. 如果当前节点为空，那么就插入当前节点，如果当前节点不为空，那么就继续递归。
     */
}

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }
        return root;                
    }
    // 迭代法 因为是要插入到叶子节点，所以需要找到叶子节点，然后插入即可, 无需栈存储模拟递归
    public TreeNode insertIntoBST1(TreeNode root, int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val > val) {
                if (cur.left == null) {
                    cur.left = new TreeNode(val);
                    break;
                } else {
                    cur = cur.left;
                }
            } else {
                if (cur.right == null) {
                    cur.right = new TreeNode(val);
                    break;
                } else {
                    cur = cur.right;
                }
            }
        }
        return root;
    }
}
